package gsw.tool.arithmetic;

import gsw.tool.common.Tool;
import gsw.tool.common.ToolShow;

/**
 * 回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
 * 回溯法常见应用：九宫格、八皇后、数独。
 *
 * @author GSW
 */
public class Backtracking {

    public static void test() {
        //测试九宫格
        int[][] arr = nineGrid(5);
        ToolShow.printArr(arr);

        //测试八皇后
        int[] arr2 = new int[8];
        eightQueens(arr2, 0);

        //测试数独
        int[][] arr3 = new int[9][9];
        sudoku(arr3, 0, 0);
    }

    /**
     * 九宫格：所有的行、列和斜线的和都相等。九宫格的边长都为奇数。
     * 规则：
     * 1.把1放到第一行的中间
     * 2.开始向右上角放入后面的数字：右上为空，直接填入；否则，填在右上角之下。如果右上超过边界，则取另一边。
     * ３.重复２操作，直到填满为止。
     *
     * @param n :九宫格的边长,为奇数。
     */
    public static int[][] nineGrid(int n) {
        //九宫格
        int[][] arr = new int[n][n];

        // 需要填入的值：把1放中间
        int x = 1;
        // 行号
        int row = 0;
        // 列号
        int col = n / 2;
        arr[row][col] = x;

        //如果x小于能填入的最大值
        while (x < n * n) {
            // 先记录原来的位置
            int tempR = row;
            int tempC = col;
            //如果超出左边，就从右边开始
            if (--row < 0) {
                row = n - 1;
            }
            //如果超出下边，就从上边开始
            if (++col == n) {
                col = 0;
            }
            //如果右上角没有填入，就填充
            if (arr[row][col] == 0) {
                arr[row][col] = ++x;
                //如果右上角已经填入数字，就填充右上角的下边
            } else {
                row = tempR;
                col = tempC;
                arr[++row][col] = ++x;// ++row一定小于n
            }
        }
        return arr;
    }

    /**
     * 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
     * 操作步骤：
     * 1. 声明一个数组M，它的下标代表皇后所在的行号，它的值代表皇后所在的列号，数组的长度代表皇后的个数；
     * 2. 从第0行开始比较，先把皇后A放在第0列，然后判断与其他行的皇后是否相交，如果相交，就把皇后A放到下一列；如果不想交，就开始放下一行的皇后B；
     * 3. 重复步骤2，知道放到最后一行，说明放好了所有皇后。
     *
     * @param arr 结果集，它的下标代表皇后所在的行号，它的值代表皇后所在的列号
     * @param row 当前行数
     */
    public static void eightQueens(int[] arr, int row) {
        if (Tool.isEmpty(arr)) {
            return;
        }
        //从第0行开始放，如果到了最后一行，说明全部放好了
        if (row == arr.length) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < arr.length; i++) {
                sb.append(i + ":" + arr[i] + ", ");
            }
            ToolShow.log(sb.toString());
            return;
        }


        // 从第0列开始放皇后
        for (int i = 0; i < arr.length; i++) {
            //把皇后放在当前行的第i列
            arr[row] = i;
            // 表示是否相交，true代表相交，false代表不相交
            boolean intersect = false;
            // 判断当前点与其他点是否相交
            for (int j = 0; j < row; j++) {
                // 在同一列或者在对角线上
                if (arr[j] == arr[row] || Math.abs(row - j) == Math.abs(arr[row] - arr[j])) {
                    intersect = true;
                    break;
                }
            }
            // 如果不相交，就与下一行比较
            if (!intersect) {
                eightQueens(arr, row + 1);
            }
        }
    }

    /**
     * 数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。
     * 操作步骤：
     * 1. 声明一个9行9列的数组M；
     * 2. 从0行0列的位置开始填数，依次把1到9入该位置，填入前线先判断填入数字1后，是否出现同行同列重复或者同子宫内重复，如果重复，就判断后面的数字2；一直到数字n能填入；然后填入下一个位置；
     * 3. 重复步骤2，直到所有数字都被填入。
     *
     * @param arr 结果集
     * @param i   当前行
     * @param j   当前列
     */
    public static void sudoku(int[][] arr, int i, int j) {
        // 到达终点就退出
        if (i == arr.length - 1 && j == arr.length) {
            ToolShow.printArr(arr);
            return;
        }

        //到了最右边，就跳到下一行
        if (j == arr.length) {
            j = 0;
            i++;
        }

        //如果当前位置没有填值
        if (arr[i][j] == 0) {
            for (int m = 1; m <= arr.length; m++) {
                //判断数字m能否填入i行j列
                if (jude(arr, i, j, m)) {
                    //先数字m填入i行j列
                    arr[i][j] = m;
                    //然后开始填入下一个位置
                    sudoku(arr, i, j + 1);
                    //如果不能够填完所有数字，就回退
                    arr[i][j] = 0;
                }
            }
            //如果当前位置有填值，就填下一个位置
        } else {
            sudoku(arr, i, j + 1);
        }

    }

    /**
     * 用来验证该数字能否填入指定位置
     *
     * @param arr    要填入的数组
     * @param row    行号
     * @param col    列号
     * @param number 需要验证的数字
     * @return true代表该数字可以填入，false代表不能填入
     */
    public static boolean jude(int[][] arr, int row, int col, int number) {
        // 判断行和列的不重复
        for (int i = 0; i < arr.length; i++) {
            // 如果有重复就返回false
            if (arr[row][i] == number || arr[i][col] == number) {
                return false;
            }
        }

        // 判断自己所在的宫里面有没有重复值
        int tempR = row / 3;
        int tempC = col / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (arr[tempR * 3 + i][tempC * 3 + j] == number) {
                    return false;
                }
            }
        }
        return true;
    }

}
